#!/usr/bin/env python3
# -*- coding: utf-8 -*-
__author__ = 'sundx'


def findLowestCost(costs):
    LowestCost = float("inf")
    LowestCostNode = None
    for node in costs:
        theCost = costs[node]
        if LowestCost > theCost and node not in processed:
            LowestCost = theCost
            LowestCostNode = node
    return LowestCostNode


# 记录节点信息
graphDemo = {"start": {"a": 6, "b": 2}, "a": {"last": 1},
             "b": {"a": 3, "last": 5}, "last": {}}
# 记录父节点
fatherDemo = {"a": "start", "b": "start", "last": ""}
# 记录每个节点的开销
costsDemo = {"a": 6, "b": 2, "last": float("inf")}
# 已经处理过的节点 （在函数findLowestCost中用来筛选）
processed = []

theNode = findLowestCost(costsDemo)
while theNode:
    theCost = costsDemo[theNode]
    nodeNeighbor = graphDemo[theNode]
    for n in nodeNeighbor.keys():
        newCost = theCost + nodeNeighbor[n]
        if costsDemo[n] > newCost:
            # 更新
            costsDemo[n] = newCost
            fatherDemo[n] = theNode
    # 讲该节点加入已处理的数组
    processed.append(theNode)
    theNode = findLowestCost(costsDemo)

print(costsDemo)
print(fatherDemo)